package dp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 139. 单词拆分
 */
public class P139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        //转储map
        int maxLen = 0;
        Map<String, Boolean> dictMap = new HashMap<>();
        for (String word : wordDict) {
            if (word.length() > maxLen) {
                maxLen = word.length();
            }
            dictMap.put(word, true);
        }
        //执行分隔
        return backTrack(s, 0, maxLen, new ArrayList<>(), dictMap);
    }

    // 动态规划
    public boolean dp(String s, List<String> wordDict) {
        //转储map
        int maxLen = 0;
        Map<String, Boolean> dictMap = new HashMap<>();
        for (String word : wordDict) {
            if (word.length() > maxLen) {
                maxLen = word.length();
            }
            dictMap.put(word, true);
        }
        // dp数组
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dictMap.containsKey(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }

    // 回溯
    private boolean backTrack(String s, int start, int maxLen, List<String> savedList, Map<String, Boolean> dictMap) {
        if (start == s.length()) {
            return true;
        } else {
            for (int i = 1; i <= maxLen; i++) {
                String sub = s.substring(start, start + i);
                if (dictMap.containsKey(sub)) {
                    savedList.add(sub);
                    boolean flag = backTrack(s, start + i, maxLen, savedList, dictMap);
                    savedList.remove(savedList.size() - 1);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }
    }


    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        boolean dp = new P139().dp(s, wordDict);
        System.out.println(dp);
    }

}
